package nowcoder.offer;

/**
 * 构建乘积数组
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-28 19:45
 */
public class Multiply {

    public int[] solution(int[] A){
        if (A == null || A.length == 0) return null;
        int len = A.length;
        int[] B = new int[len];
        for (int i = 0; i < len; i++) {
            int left = 1,right = 1;
            for (int j = 0; j < i; j++) {
                left *= A[j];
            }
            for (int j = i+1; j < len; j++) {
                right *= A[j];
            }
            B[i] = left * right;
        }

        return B;
    }

    public int[] solution2(int[] A){
        if (A == null || A.length == 0) return null;
        int len = A.length;
        int[] B = new int[len];
        int[] sum1 = new int[len+1]; //sum[i] 表示 A[0]*...A[i]
        int[] sum2 = new int[len+1]; //sum2[i] 表示 A[i]*...A[len-1];
        sum1[0] = A[0];
        sum2[len] = 1;
        for (int i = 1; i < len; i++) {
            sum1[i] = sum1[i-1] * A[i];
            sum2[len-i] = sum2[len-i+1] * A[len-i];
        }

        B[0] = sum2[1];
        B[len-1] = sum1[len-2];
        for (int i = 1; i < len-1; i++) {
            B[i] = sum1[i-1] * sum2[i+1];
        }

        return B;
    }

    public static void main(String[] args) {
        new Multiply().solution2(new int[]{1,2,3,4,5});
    }
}
